1. Field of the Invention
This invention relates generally to methods and apparatus for performing a cyclic redundancy check (CRC) and more particularly to a method and apparatus for performing a CRC process on data that is received out of order without having to store and assemble the data in order to perform the CRC.
2. Description of the Related Art
Digital data transmission systems are used in a variety of different applications touching all aspects of a person's daily activities. These systems range from transferring money through bank accounts to storing the music on compact digital audio discs. It is imperative to be able to check whether the transmitted data is received without errors. More particularly, without the capability to check if transmitted data is received without errors, the transfer of funds electronically would be an unacceptably high risk. Thus, there would be severe consequences for the world financial system without error detection capability.
One method for error detection is the cyclic redundancy check (CRC) method. A transmitting device calculates a CRC for a message to be transmitted. The CRC, which is a sequence of bits, is appended to the message being transmitted. On the receiving end, a CRC is recalculated by the receiving device and this CRC is compared to the received CRC to determine if an error has occurred. FIG. 1 is a diagram depicting the prior art execution of a CRC method. Data stream 102, which consists of words A–H, is being received by a device. CRC 104 is appended to the end of data stream 102 by the transmitting device. The receiving device performs the CRC in sequential order of a data stream. As illustrated in FIG. 1, a CRC is performed one word at a time in sequential order. Therefore, a CRC is performed on word A, then the result is combined with word B and a CRC is performed with the result then being combined with word C and so on. After completion of word H, a remainder is inverted and appended to the end of data stream 102 as represented by CRC 104. As is well known, the Ethernet CRC algorithm performs the steps described above with respect to FIG. 1.
FIG. 2 represents a prior art diagram of the sequential processing nature of a CRC method for data stream 102. Data stream 102 is processed sequentially by CRC engine 106 where each word of data steam 102 is processed to obtain CRC remainder 108. CRC remainder 108 for each word or packet is then combined with the next word or packet in sequential order. This process is repeated until the end of data stream 102 is reached as described with respect to FIG. 1. At the completion of the process a remainder is inverted by inverter 107 to provide a complete CRC 109 which is appended to the end of data stream 102.
With respect to the prior art, data stream 102 must be processed sequentially. However, when large data streams are sent over a channel they are split into small-sized segments during transmission. This is especially true with distributed networks over a wide area such as the Internet where packets or cells of data can be sent by different routes, thus these packets may be received at the destination out of sequential order. Consequently, the small-sized segments, i.e., packets or cells, must be stored in local memory where it can be reassembled in the original sequential order once the complete data stream is received. Once the data stream is assembled in order then the CRC is performed. Moreover, with the accelerating adoption of Internet Small Computer System Interface (iSCSI), a storage networking standard for linking data storage facilities, which transmits protocol data units (PDU) made up of separate packets, the delays may become longer depending on the amount of data being transmitted and at the same time the memory capacity will need to be increased to handle the large amounts of data transmitted. Thus, a longer delay is incurred while waiting for the entire data stream to be received and more of the capacity of the local memory is being consumed to store the data stream.
In view of the foregoing, there is a need to perform CRC on segments or packets of a data stream without having to assemble the data stream in its original sequential order.